t = int(input())
while t:
n, k = input().split()
s = input()
flag = True
for i in range(int(n)//2):
if s[i]!=s[int(n)-1-i]: flag = False; break
if flag or int(k) == 0: print(1)
else: print(2)
t -= 1#include <bits/stdc++.h>
using namespace std;
int main()
{
int t; cin >>t;
while (t--)
{
int n,k; cin >>n>>k;
char x[n];
for (int i=0;i<n;i++)
cin >>x[i];
int a=0;
for (int i=0;i<n;i++,n--)
{
if (i>n) break;
if (x[i]!=x[n-1])
{a++;break;}
if (i==n) break;
}
if (a==0 || k==0)
cout <<1<<endl;
else
cout <<2<<endl;
}
return 0;
}1A - Theatre Square | 1614B - Divan and a New Project |
791A - Bear and Big Brother | 1452A - Robot Program |
344A - Magnets | 96A - Football |
702B - Powers of Two | 1036A - Function Height |
443A - Anton and Letters | 1478B - Nezzar and Lucky Number |
228A - Is your horseshoe on the other hoof | 122A - Lucky Division |
1611C - Polycarp Recovers the Permutation | 432A - Choosing Teams |
758A - Holiday Of Equality | 1650C - Weight of the System of Nested Segments |
1097A - Gennady and a Card Game | 248A - Cupboards |
1641A - Great Sequence | 1537A - Arithmetic Array |
1370A - Maximum GCD | 149A - Business trip |
34A - Reconnaissance 2 | 59A - Word |
462B - Appleman and Card Game | 1560C - Infinity Table |
1605C - Dominant Character | 1399A - Remove Smallest |
208A - Dubstep | 1581A - CQXYM Count Permutations |